#include <iostream>
#include <unordered_set>

struct ListNode
{
    int val;
    ListNode*next;
};

ListNode*solve(ListNode*&head)
{
    // 首先判空或者只有一个节点
    if (!head||!head->next) return head;

    // 接下来使用unordered_set进行去重
    std::unordered_set<int>us;

    // 遍历链表 复杂度 O(n)
    ListNode*temp = head;
    ListNode*prior = nullptr;
    while (temp)
    {
        if (us.find(temp->val)!=us.end())
        {
            ListNode*to_delete = temp;
            prior->next = temp->next;
            temp = prior->next;
        }
        else 
        {
            us.insert(temp->val);
            prior = temp;
            temp = temp->next;
        }
    }
}

void print_list(ListNode*head)
{
    ListNode*temp = head;
    while (temp)
    {
        std::cout<<temp->val<<" ";
        temp = temp->next;
    }
    std::cout<<std::endl;
}

void add_node(ListNode*&head,int data)
{
    // 不用写注释(
    ListNode*node = new ListNode;
    node->val = data;
    node->next = nullptr;
    if (!head) head = node;

    ListNode*temp = head;
    while (temp->next)
    {
        temp = temp->next;
    }

    temp->next = node;
}

int main()
{
    ListNode*head = new ListNode;
    head->val = 2;
    for (int i = 0; i < 3;i++)
    {   
        add_node(head,1);
    }
    print_list(head);

    // 进行去重
    solve(head);

    // 
    print_list(head);
    return 0;
}